\tikzset{
    treenode/.style = {align=center, inner sep=0pt, text centered,

    :@a





q
            font=\sffamily},
    node_b/.style = {treenode, circle, blue, font=\sffamily\bfseries, draw=blue,
            fill=white, text width=2.5em,thick},% arbre rouge noir, noeud noir
    arn_b/.style = {treenode, circle, red, draw=red,
            text width=2.5em, thick},% arbre rouge noir, noeud rouge
    arn_x/.style = {treenode, rectangle, draw=black,
            minimum width=0.5em, minimum height=0.5em}% arbre rouge noir, nil
}

\subsection{递归的复杂度分析}
给出一个递归算法，其时间复杂度 $\mathcal{O}(T)$通常是递归调用的数量（记作 $R$） 和计算的时间复杂度的乘积（表示为 $\mathcal{O}(s)$）的乘积：
\begin{equation}
    \mathcal{O}(T) = R \cdot \mathcal{O}(s)
\end{equation}
我们来看看下面的一些例子。也许你还记得，在反转字符串问题中，我们需要以相反的顺序打印字符串，解决问题的递归关系可以表示如下：
\begin{equation}
    printReverse(str) = printReverse(str[1...n]) + print(str[0])
\end{equation}

其中 $str[1...n]$ 是输入字符串 str 的子串，仅不含前导字符 $str[0]$。如您所见，该函数将被递归调用 $n$ 次，其中 $n$ 是输入字符串的大小。在每次递归结束时，我们只是打印前导字符，因此该特定操作的时间复杂度是恒定的，即 $\mathcal{O}(1)$。总而言之，我们的递归函数 $printReverse(str)$ 的总体时间复杂度为 $\mathcal{O}(printReverse) = n \cdot \mathcal{O}(1) = \mathcal{O}(n)$。

\subsubsection{执行树}
对于递归函数，递归调用的数量很少与输入的大小呈线性关系。如果你还记得我们在前一章中讨论过的斐波那契数问题，其递推关系被定义为 $f(n) = f(n-1) + f(n-2)$。乍一看，在执行斐波那契函数期间计算递归调用的数量似乎并不简单。在这种情况下，最好采用执行树，这是一个用于表示递归函数的执行流程的树。树中的每个节点都表示递归函数的调用。因此，树中的节点总数对应于执行期间的递归调用的数量。递归函数的执行树将形成 n 叉树，其中 n 作为递推关系中出现递归的次数。例如，斐波那契函数的执行将形成二叉树，下面的\figref{fig:执行树}示展现了用于计算斐波纳契数 $f(4)$ 的执行树。在 n 层的完全二叉树中，节点的总数为 $2^n -1$。因此 $f(n)$ 中递归数目的上限（尽管不严格）也是 $2^n -1$。那么我们可以估计 $f(n)$ 的时间复杂度为 $\mathcal{O}(2^n)$。
\begin{figure}[H]
    \centering
    \begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
                    level distance = 1.5cm}]
        \node [node_b] {fib(4)}
        child{ node [arn_b] {fib(3)}
                child{ node [node_b] {fib(2)}
                        child{ node [arn_b] {fib(1)} edge from parent node[above left]
                                    {}} %for a named pointer
                        child{ node [arn_b] {fib(0)}}
                    }
                child{ node [node_b] {fib(1)}
                    }
            }
        child{ node [arn_b] {fib(2)}
                child{ node [node_b] {fib(1)}
                    }
                child{ node [node_b] {fib(0)}
                    }
            }
        ;
    \end{tikzpicture}
    \caption{执行树}
    \label{fig:执行树}
\end{figure}

\subsubsection{记忆化（Memoization）}
在前一章中，我们讨论了通常用于优化递归算法的时间复杂度的记忆化技术。过高速缓存和重用中间结果，记忆化技术可以大大减少递归调用的数量，即减少执行树中的分支数量。在使用记忆化分析递归算法的时间复杂度时，也应该考虑到这种减少。让我们回到斐波纳契数的例子。通过记忆化技术，我们保存每个索引 $n$ 对应的的斐波那契数的结果。我们确信每个斐波那契数的计算只会发生一次。而从递推关系来看，斐波纳契数 $f(n)$ 将取决于其所有 $n-1$ 个先验斐波纳契数。结果，计算 $f(n)$ 的递归将被调用 $n-1$ 次以计算它所依赖的所有先验数字。现在，我们可以简单地应用我们在本章开头介绍的公式来计算时间复杂度，即 $\mathcal{O}(1) * n = \mathcal{O}(n)$。记忆化技术不仅可以优化算法的时间复杂度，还可以简化时间复杂度的计算。

\subsubsection{递归相关空间}
递归相关空间是指由递归直接引起的内存开销，即用于跟踪递归函数调用的堆栈。为了完成典型的函数调用，系统应该在栈中分配一些空间来保存三个重要信息：
\begin{enumerate}
    \item 函数调用的返回地址。一旦函数调用完成，程序应该知道返回的位置，即函数调用之前的点。
    \item 传递给函数调用的参数。
    \item 函数调用中的局部变量。
\end{enumerate}
栈中的这个空间是函数调用期间产生的最小成本。然而，一旦完成函数调用，就会释放该空间。对于递归算法，函数调用将连续链接直到它们到达基本情况（也称为 底层情况）。这意味着用于每个函数调用的空间也会累积。对于递归算法，如果没有产生其他内存消耗，则此递归引起的空间将是算法的空间上限。

例如，在练习反转字符串中，我们没有使用额外的内存，因为我们仅仅是打印一个字符。对于每个递归调用，我们假设它可能需要一个最大为某一常量值的空间。并且递归调用最多可以链接 $n$ 次，其中 $n$ 是输入字符串的大小。因此，该递归算法的空间复杂度就是 $\mathcal{O}(n)$。为了更好地说明这一点，接下来我们将会展示递归调用$ f(x_1) -> f(x_2) -> f(x_3) $的执行顺序以及栈空间的分配情况。

栈中的空间将会分配给 $f(x_1)$ 来调用 $f(x_2)$。类似的情况也同样发生在 $f(x_2)$ 中，系统会为 $f(x_3)$ 的调用分配另一个空间，最后在 $f(x_3)$ 中，我们到达基本情况，因此在 $f(x_3)$ 中没有进行进一步的递归调用。正是由于这些与递归相关的空间消耗，有时可能会遇到称为堆栈溢出的情况，其中为程序分配的堆栈达到其最大空间限制并导致程序最终失败。在设计递归算法时，应该仔细评估在输入规模扩大时是否存在堆栈溢出的可能性。
\subsubsection{非递归相关空间}
正如名称所示，非递归相关空间指的是与递归过程没有直接关系的内存空间，通常包括为全局变量分配的空间（通常在堆中）。不管是否递归，你都可能需要在任何函数调用之前将问题的输入存储为全局变量。你可能还需要保存递归调用的中间结果。后者就是我们前面提到过的记忆化技术。例如，在使用带有记忆化技术的递归算法解决斐波那契数问题时,我们使用映射（map）来跟踪在递归调用期间产生的所有中间斐波那契数。因此，在分析空间复杂度时，我们应该考虑到因采用记忆化技术所导致的空间成本。
在上一篇文章中，我们讨论了由于递归调用而在系统调用栈上产生的隐式额外空间。然而，你应该学习识别一种称为尾递归的特殊递归情况，它不受此空间开销的影响。
\subsubsection{尾递归}
尾递归函数是递归函数的一种，其中递归调用是递归函数中的最后一条指令。并且在函数中应该只有一次递归调用。我们已经在反转字符串的解决方案中看到了尾递归的例子。这里的另一个例子说明了非尾递归和尾递归之间的区别。请注意，非尾递归示例中，在最后一次递归调用之后有一个额外的计算。尾递归的好处是，它可以避免递归调用期间栈空间开销的累积，因为系统可以为每个递归调用重用栈中的固定空间。

例如，对于递归调用序列 $f(x_1) -> f(x_2) -> f(x_3)$，如果函数 $f(x)$ 以尾递归的形式实现。那么其执行步骤的顺序和栈空间的分配如下所示：

请注意，在尾递归的情况下，一旦从递归调用返回，我们也会立即返回，因此我们可以跳过整个递归调用返回链，直接返回到原始调用方。这意味着我们根本不需要所有递归调用的调用栈，这为我们节省了空间。

例如，在步骤（1）中，栈中的一个空间将被分配给 $f(x_1)$，以便调用 $f(x_2)$。然后，在步骤（2）中，函数 $f(x_2)$ 能够递归地调用 $f(x_3)$，但是，系统不需要在栈上分配新的空间，而是可以简单地重用先前分配给第二次递归调用的空间。最后，在函数 $f(x_3)$ 中，我们达到了基本情况，该函数可以简单地将结果返回给原始调用方，而不会返回到之前的函数调用中。

尾递归函数可以作为非尾递归函数来执行，也就是说，带有调用栈并不会对结果造成影响。通常，编译器会识别尾递归模式，并优化其执行。然而，并不是所有的编程语言都支持这种优化，比如 C，C++ 支持尾递归函数的优化。另一方面，Java 和 Python 不支持尾递归优化。

\begin{example}{台阶跳问题}
    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
\end{example}
解法1（暴力法）：在暴力法中，我们将会把所有可能爬的阶数进行组合，也就是 1 和 2 。而在每一步中我们都会继续调用 $climbStairsclimbStairs$ 这个函数模拟爬 1 阶和 2 阶的情形，并返回两个函数的返回值之和。
\begin{equation}
    climbStairs(i,n)=climbStairs(i+1,n)+climbStairs(i+2,n)
\end{equation}
其中$i$为当前的台阶数，$n$定义了目标台阶数。这个问题可变成达到$climbStairs(i,n)$会有两种情况，一种是$climbStairs(i+1,n)$ （当前台阶为i，走一阶台阶后达到目标n），另一情况为$climbStairs(i+2,n)$（当前台阶为i，走2阶台阶后达到目标n的走法）的和。当目标台阶为4的时候执行树如下\figref{fig:execute_tree}：
\begin{figure}[H]
    \centering
    \begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
                    level distance = 1.5cm}]
        \node [node_b] {f(0,4)}
        child{ node [arn_b] {f(1,4)}
                child{ node [node_b] {f(2,4)}
                        child{ node [arn_b] {f(3,4)} edge from parent node[above left]
                                    {}} %for a named pointer
                        child{ node [arn_b] {f(4,4)}}
                    }
                child{ node [node_b] {f(3,4)}
                    }
            }
        child{ node [arn_b] {f(2,4)}
                child{ node [node_b] {f(3,4)}
                    }
                child{ node [node_b] {f(4,4)}
                    }
            }
        ;
    \end{tikzpicture}
    \caption{目标台阶为4的执行树}
    \label{fig:execute_tree}
\end{figure}
树上每一点均需要一次计算，最坏情况下（完全二叉树）的节点书为$2^n$。时间复杂度为$O(z^n)$。空间复杂度$O(n)$，递归数的深度可以达到n。

方法2：记忆化（减少重复计算）

此方法主要是将中间的计算结果缓存，每次需要的时候直接从缓存获取数据以避免重复计算。因为计算不需要迭代，所以计算第n个结果的时候只要知道前面n-1个结果即可。
时间复杂度为$O(n)$，空间复杂度为$O(n)$用来缓存数据。

方法3：动态规划

不难发现，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，我们可以使用动态规划来解决这一问题。我们要知道
到台阶$n$的可能走法$f(n)$，可以把此问题看作台阶到达台阶$n-1$的走法$f(n-1)$和台阶$n-2$后$f(n-2)$的走法。即到达台阶$n$，可以选择到达$n-1$后然后走一阶和到达$n-2$后爬一阶。为什么是一阶？如果到$n-2$后再爬两个一阶就和$f(n-1)$重复了。所以递推方程为：
\begin{equation*}
    f(n) =\begin{cases}
         & f(n-1)+f(n-2)\quad n\geq 2 \\
         & 1 \quad n = 1              \\
         & 0 \quad n = 0
    \end{cases}
\end{equation*}
动态规划的递推方式和斐波拉契数列类似。该算法需要通过前n个元素获取最后一个元素的值，时间复杂度为$O(n)$，空间复杂度为$O(1)$（之保留两个需要计算的元素）。

方法4：数学方法
不难看出我们的目的是求解差分方程（斐波拉契数列从n=1开启取值）：
\begin{equation*}
    fn(n)=
    \begin{cases}
         & f(n-2)+f(n-1)\quad n\geq2 \\
         & 1 \quad 1                 \\
         & 0 \quad 0
    \end{cases}
\end{equation*}
通过求解Z变换计算Z域的零点。我们可以得到如下方程：
\begin{equation*}
    F(Z) = Z^{-1}F(Z-1)+Z^2F(Z-2) = (Z^2-Z-1)F(Z) = 0\\
\end{equation*}
计算零点：
\begin{equation*}
    Z_1 = \frac{1+\sqrt{5}}{2}\\
    Z_2 = \frac{1-\sqrt{5}}{2}
\end{equation*}
时域表达式：
\begin{equation*}
    f(n) = A(Z_1)^n+B(Z_2)^n
\end{equation*}
通过初始条件$f(0) = 1,f(1) = 1$可以计算的出$f(n) = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right)$
时间复杂度：$O(log(n))$，空间复杂度$O(1)$。

\subsection{C++20 迭代器概念}
C++20 引入基于概念的新迭代器系统，它异于 C++17 迭代器。虽然基础分配法保持类似，但单独的迭代器类别的要求有些区别。定义于命名空间 std。
\begin{itemize}
	\item \href{https://zh.cppreference.com/w/cpp/iterator/indirectly_readable}{indirectly\_readable} (C++20)：指定类型通过应用运算符 * 可读(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/indirectly_writable}{indirectly\_writable}(C++20)：指定可向迭代器所引用的对象写入值(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/weakly_incrementable}{weakly\_incrementable}(C++20)：指定 semiregular 类型能以前后自增运算符自增(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/incrementable}{incrementable}(C++20)：指定 weakly\_incrementable 类型上的自增操作保持相等性，而且该类型为 equality\_comparable(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/input_or_output_iterator}{input\_or\_output\_iterator}(C++20)：指定该类型对象可以自增且可以解引用(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/sentinel_for}{sentinel\_for}(C++20)：指定类型为某个 input\_or\_output\_iterator 类型的哨位类型(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/sized_sentinel_for}{sized\_sentinel\_for}:(C++20)指定可对一个迭代器和一个哨位应用 - 运算符，以在常数时间计算其距离(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/input_iterator}{input\_iterator}:(C++20)指定类型为输入迭代器，即可读取其所引用的值，且可前/后自增(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/output_iterator}{output\_iterator}:(C++20)指定类型为给定的值类型的输出迭代器，即可向其写入该类型的值，且可前/后自增(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/forward_iterator}{forward\_iterator}:(C++20)指定 input\_iterator 为向前迭代器，支持相等比较与多趟操作(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/bidirectional_iterator}{bidirectional\_iterator}(C++20)：指定 forward\_iterator 为双向迭代器，支持向后移动(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/random_access_iterator}{random\_access\_iterator}(C++20)：指定 bidirectional\_iterator 为随机访问迭代器，支持常数时间内的前进和下标访问(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/contiguous_iterator}{contiguous\_iterator}(C++20)：指定 random\_access\_iterator 为连续迭代器，指代内存中连续相接的元素(概念)
\end{itemize}
\subsection{迭代器关联类型}
定义于命名空间 std
\begin{itemize}
	\item \href{https://zh.cppreference.com/w/cpp/iterator/incrementable_traits}{incrementable\_traits}(C++20):计算 weakly\_incrementable 类型的差类型(类模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/indirectly_readable_traits}indirectly\_readable\_traits}(C++20)：计算 indirectly\_readable 类型的值类型(类模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/iter_t}{iter\_value\_t iter\_reference\_t、iter\_difference\_t、iter\_rvalue\_reference\_t、iter\_common\_reference\_t}（C++20）:计算迭代器的关联类型(别名模板)
\end{itemize}
\subsubsection{迭代器原语}
\begin{itemize}
	\item \href{https://zh.cppreference.com/w/cpp/iterator/iterator_traits}{iterator\_traits}：为迭代器各项性质提供统一接口(类模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/iterator_tags}{input\_iterator\_tag、output\_iterator\_tag、forward\_iterator\_tag、bidirectional\_iterator\_tag、random\_access\_iterator\_tag、contiguous\_iterator\_tag}(C++20)：用于指示迭代器类别的空类类型(类)
\end{itemize}
\subsubsection{迭代器定制点}
定义于命名空间 std::ranges
\begin{itemize}
	\item \href{https://zh.cppreference.com/w/cpp/iterator/ranges/iter_move}{iter\_move}(C++20)：将解引用迭代器的结果转型为其关联的右值引用类型(定制点对象)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/ranges/iter_swap}{iter\_swap}(C++20)：交换两个可解引用对象所引用的值(定制点对象)
\end{itemize}
\subsubsection{算法概念与工具}
C++20 亦提供简化常用算法操作的约束而设计的概念和工具模板集合。定义于头文件 <iterator>,定义于命名空间 std。间接可调用对象
\begin{itemize}
	\item \href{https://zh.cppreference.com/w/cpp/iterator/indirectly_unary_invocable}{indirectly\_unary\_invocable、indirectly\_regular\_unary\_invocable}(C++20)：指定可调用类型能以解引用某个 indirectly_readable 类型的结果进行调用(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/indirect_unary_predicate}{indirect\_unary\_predicate}(C++20)：指定可调用类型，在以解引用一个 indirectly\_readable 类型的结果进行调用时，满足 predicate(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/indirect_binary_predicate}{indirect\_binary\_predicate}(C++20)：指定可调用类型，在以解引用两个 indirectly\_readable 类型的结果进行调用时，满足 predicate(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/indirect_equivalence_relation}{indirect\_equivalence\_relation}(C++20)：指定可调用类型，在以解引用两个 indirectly\_readable 类型的结果进行调用时，满足 equivalence\_relation(概念)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/indirect_strict_weak_order}{indirect\_strict\_weak\_order}(C++20)：指定可调用类型，在以解引用两个 indirectly\_readable 类型的结果进行调用时，满足 strict\_weak\_order(概念)
\end{itemize}
\subsubsection{常用算法要求}
\begin{itemize}
	\item \href{https://zh.cppreference.com/w/cpp/iterator/indirectly_movable}{indirectly\_movable}(C++20)：指定可从 indirectly\_readable 类型移动值给 indirectly\_writable 类型(概念)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/indirectly_movable_storable}{indirectly\_movable\_storable}(C++20)：指定可从 indirectly\_readable 类型复制值给 indirectly\_writable 类型(概念)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/indirectly_copyable}{indirectly\_copyable}(C++20)：指定可从 indirectly\_readable 类型复制值给 indirectly\_writable 类型(概念)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/indirectly_copyable_storable}{indirectly\_copyable\_storable}(C++20)：指定可从 indirectly\_readable 类型复制值给 indirectly\_writable 类型，且该复制可以通过中间对象进行(概念)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/indirectly_comparable}{indirectly\_swappable}(C++20)：指定能交换两个 indirectly\_readable 类型所引用的值(概念)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/indirectly_comparable}{indirectly\_comparable}(C++20)：指定能比较两个 indirectly\_readable 类型所引用的值(概念)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/permutable}{permutable}(C++20)：指定在原位重排元素的算法的共同要求(概念)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/mergeable}{mergeable}(C++20)：指定通过复制元素将已排序序列归并到输出序列中的算法的要求(概念)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/sortable}{sortable}(C++20)：指定重排序列为有序序列的算法的共用要求(概念)
\end{itemize}
\subsubsection{工具}
\begin{itemize}
	\item \href{https://zh.cppreference.com/w/cpp/iterator/indirect_result_t}{indirect\_result\_t}(C++20)：计算在解引用某组 indirectly_readable 类型的结果上调用可调用对象的结果(别名模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/projected}{projected}(C++20)：用于对接受投影的算法指定约束的辅助模板(类模板)
\end{itemize}
\subsubsection{迭代器适配器}
\begin{itemize}
	\item \href{https://zh.cppreference.com/w/cpp/iterator/reverse_iterator}{reverse\_iterator}逆序遍历的迭代器适配器：类模板)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/make_reverse_iterator}{make\_reverse\_iterator}(C++14)创建拥有从实参推出的类型的 std::reverse\_iterator(函数模板)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/move_iterator}{move\_iterator}(C++11)解引用结果为右值引用的迭代器适配器(类模板)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/move_sentinel}{move\_sentinel}(C++20)：用于 std::move\_iterator 的哨位适配器(类模板)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/make_move_iterator}{make\_move\_iterator}(C++11)：创建拥有从实参推出的类型的 std::move\_iterator(函数模板)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/common_iterator}{common\_iterator}(C++20)：适配一个迭代器类型及其哨位为一个公共迭代器类型(类模板)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/default_sentinel_t}{default\_sentinel\_t}(C++20)：用于知晓其边界的迭代器的默认哨位(类)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/counted_iterator}{counted\_iterator}(C++20)：对到范围结尾距离进行跟踪的迭代器适配器(类模板)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/unreachable_sentinel_t}{unreachable\_sentinel\_t}(C++20)：始终与任何 weakly\_incrementable 类型比较都不相等的哨位(类)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/back_insert_iterator}{back\_insert\_iterator}用于在容器尾部插入的迭代器适配器(类模板)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/back_inserter}{back\_inserter}创建拥有从实参推出的类型的 std::back\_insert\_iterator(函数模板)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/front_insert_iterator}{front\_insert\_iterator}：用于在容器头部插入的迭代器适配器(类模板)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/front_inserter}{front\_inserter}：创建拥有从实参推出的类型的 std::front\_insert\_iterator(函数模板)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/insert_iterator}{insert\_iterator}：用于插入容器的迭代器适配器(类模板)
	\item  \href{https://zh.cppreference.com/w/cpp/iterator/inserter}{inserter}：创建拥有从实参推出的类型的 std::insert\_iterator(函数模板)
\end{itemize}
\subsubsection{流迭代器}
\begin{itemize}
	\item \href{https://zh.cppreference.com/w/cpp/iterator/istream_iterator}{istream\_iterator}：从 std::basic\_istream 读取的输入迭代器(类模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/ostream_iterator}{ostream\_iterator}：写入 std::basic\_ostream 的输出迭代器(类模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/istreambuf_iterator}{istreambuf\_iterator}：从 std::basic\_streambuf 读取的输入迭代器(类模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/ostreambuf_iterator}{ostreambuf\_iterator}：写入 std::basic\_streambuf 的输出迭代器(类模板)
\end{itemize}

\subsubsection{迭代器操作}
定义于头文件 <iterator>
\begin{itemize}
	\item \href{https://zh.cppreference.com/w/cpp/iterator/advance}{advance}：迭代器前进给定的距离(函数模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/distance}{distance}：返回两个迭代器间的距离(函数模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/next}{next}(C++11)：令迭代器自增(函数模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/prev}{prev}(C++11)：令迭代器自减(函数模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/ranges/advance}{ranges::advance}(C++20)：令迭代器前进给定的距离或到给定的边界(niebloid)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/ranges/distance}{ranges::distance}(C++20)：返回迭代器与哨位间的距离，或范围起始与结尾间的距离(niebloid)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/ranges/next}{ranges::next}(C++20)：自增迭代器给定的距离或到边界(niebloid)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/ranges/prev}{ranges::prev}(C++20)：自减迭代器给定的距离或到边界(niebloid)
\end{itemize}
\subsubsection{范围访问}
这些非成员函数提供对容器、通常数组，及 std::initializer\_list 的通用接口。
\begin{Textcode}
定义于头文件 <array>
定义于头文件 <deque>
定义于头文件 <forward_list>
定义于头文件 <iterator>
定义于头文件 <list>
定义于头文件 <map>
定义于头文件 <regex>
定义于头文件 <set>
定义于头文件 <span>
定义于头文件 <string>
定义于头文件 <string_view>
定义于头文件 <unordered_map>
定义于头文件 <unordered_set>
定义于头文件 <vector>
\end{Textcode}
定义于命名空间 std
\begin{itemize}
	\item \href{https://zh.cppreference.com/w/cpp/iterator/begin}{begin}(C++11)、cbegin(C++14)：返回指向容器或数组起始的迭代器(函数模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/end}{end}（C++11）、cend(C++14)：返回指向容器或数组结尾的迭代器(函数模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/rbegin}{rbegin、crbegin}(C++14)：返回指向一个容器或数组的逆向迭代器(函数模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/rend}{rend、crend}(C++14)：返回容器或数组的逆向尾迭代器(函数模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/size}{size}(C++17)、ssize(C++20)：返回容器或数组的大小(函数模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/empty}{empty}(C++17)：检查容器是否为空(函数模板)
	\item \href{https://zh.cppreference.com/w/cpp/iterator/data}{data}(C++17)：获得指向底层数组的指针(函数模板)
\end{itemize}
\begin{Textcode}
定义于头文件 <ranges>
定义于头文件 <iterator>
定义于命名空间 std::ranges
\end{Textcode}
\item \href{https://zh.cppreference.com/w/cpp/ranges/begin}{ranges::begin}(C++20)：返回指向范围起始的迭代器(定制点对象)
\item \href{https://zh.cppreference.com/w/cpp/ranges/cbegin}{ranges::cbegin}(C++20)：返回指向只读范围起始的迭代器(定制点对象)
\item \href{https://zh.cppreference.com/w/cpp/ranges/end}{ranges::end}(C++20)：返回指示范围结尾的哨位(定制点对象)
\item \href{https://zh.cppreference.com/w/cpp/ranges/cend}{ranges::cend}(C++20)：返回指示只读范围结尾的哨位(定制点对象)
\item \href{https://zh.cppreference.com/w/cpp/ranges/rbegin}{ranges::rbegin}(C++20)：返回指向范围的逆向迭代器(定制点对象)
\item \href{https://zh.cppreference.com/w/cpp/ranges/crbegin}{ranges::crbegin}(C++20)：返回指向只读范围的逆向迭代器(定制点对象)
\item \href{https://zh.cppreference.com/w/cpp/ranges/rend}{ranges::rend}(C++20)：返回指向范围的逆向尾迭代器(定制点对象)
\item \href{https://zh.cppreference.com/w/cpp/ranges/crend}{ranges::crend}(C++20)：返回指向只读范围的逆向尾迭代器(定制点对象)
\item \href{https://zh.cppreference.com/w/cpp/ranges/size}{ranges::size}(C++20)：返回等于范围大小的整数(定制点对象)
\item \href{https://zh.cppreference.com/w/cpp/ranges/ssize}{ranges::ssize}(C++20)：返回等于范围大小的有符号整数(定制点对象)
\item \href{https://zh.cppreference.com/w/cpp/ranges/empty}{ranges::empty}(C++20)：检查范围是否为空(定制点对象)
\item \href{https://zh.cppreference.com/w/cpp/ranges/data}{ranges::data}(C++20)：获得指向连续范围的起始的指针(定制点对象)
\item \href{https://zh.cppreference.com/w/cpp/ranges/cdata}{ranges::cdata}(C++20)：获得指向只读连续范围的起始的指针(定制点对象)
\end{itemize}
